#include <queue>
#include <forward_list>
#include <algorithm>
#include <stdio.h>
#include "graph.h"
#include "priority-queue.tpl.h"
#include "pqueue-widx.h"
#include "disjoint-set.h"

using namespace std;
using CmpFunc=PQueueWidx::CmpFunc;

bool Graph::lv_olp_hhz(void) { 
    vector<int>degree(lv.size(), 0); //结点的度
    lv2lfs();
    for(int i=0; i<lv.size(); i++) { 
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            if(i>*it) continue;
            //emtx[i][*it]++;
            //emtx[*it][i]++;
            degree[i]++;
            degree[*it]++; 
        }
    }
    vector<int>jp; //奇度数点向量
    lv_bfs(0); //广度搜索判断连通性
    for(int i=0; i<lv.size(); i++) {
        if(degree[i]&0x1) {
            jp.push_back(i);
        }
        if(vc[i] == GVWHITE) return false;
    }
    int s = 0; //欧拉路径起点
    if(jp.size()==2) s = jp[0];
    else if(jp.size()) return false;
    vs = {};
    lv_olp_hhz_core(s);
    return true;   
}

void Graph::lv_olp_hhz_core(int u) {
    
    for(int eid = head[u]; ~eid; ) {
        int v = ev[eid][0];
        if(v<0) {
            eid = ev[eid][1];
            continue;
        }
        ev[eid][0] = -1; //标记边已经访问过
        ev[eid^1][0] = -1; //同一条边的两种形式
        head[u] = ev[eid][1]; //再次访问同一点时加快邻接边的遍历
        lv_olp_hhz_core(v);
        eid = head[u];
    }
    head[u] = -1; //再次访问时直接跳过。
    vs.push(u);
}

void Graph::lv2lfs(void) { //邻接链表转链式前向星(link front start)
    ev.resize(0);
    head = vector<int>(lv.size(), -1);
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].rbegin(); it!=lv[i].rend(); it++) {
            add_edge(i, *it);
        }
    }
}




void Graph::add_edge(int u, int v) {
    if(is_dird) {
        ADD_EDGE:
        ev.push_back(GEdge{v, head[u]});
        head[u] = ev.size()-1;
    }else if(u<=v) {
        ev.push_back(GEdge{u, head[v]});
        head[v] = ev.size()-1;
        goto ADD_EDGE;
    }
}


int Graph::lv_cag_mlsp(void) {
    lv_bfs(0);
    int mv = 0; //最远结点
    for(int i=1; i<lv.size(); i++) {
        if(bd[i] > bd[mv])
            mv = i;
    }
    dv = mv;
    lv_bfs(dv);
    mv = 0;
    for(int i=1; i<lv.size(); i++) {
        if(bd[i] > bd[mv])
            mv = i;
    }
    return mv;
}

int Graph::lv_dag_simle_paths(int s, int d) {
    lv_tp_order();
    int i = lv.size()-1;
    while(i>=0 && tporder[i] != d) {
        i--;
    }
    vector<int> pathdp(lv.size(), 0);
    pathdp[d] = 1;
    while(--i >= 0) {
        for(auto it=lv[tporder[i]].begin(); it!=lv[tporder[i]].end(); it++) {
            pathdp[tporder[i]] += pathdp[*it];
        }
        if(tporder[i]==s) break;
    }
    return pathdp[s];
}

void Graph::lv_print(void) {
    for(int i=0; i<lv.size(); i++) {
        printf("%2d:", i);
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            printf("%3d", *it);
        }
        putchar('\n');
    }
}

void Graph::mtx_print(void) {
    printf("%2s", " ");
    for(int i=0; i<mtx.size(); i++) {
        printf("%3d", i);
    }
    putchar('\n');
    for(int i=0; i<mtx.size(); i++) {
        printf("%2d", i);
        for(int j=0; j<mtx.size(); j++) {
            printf("%3d", (int)mtx[i][j]);
        }
        putchar('\n');
    }
}

void Graph::lv_mflow_pr_push(int u, int v) {
    double pf = min(ef[u], cfm[u][v]); //push flow
    if(mtx[u][v]) {
        fm[u][v] += pf;
    }else {
        fm[v][u] -= pf;
    }
    ef[u] -= pf;
    ef[v] += pf;
    cfm[u][v] -= pf;
    cfm[v][u] += pf;
}

void Graph::lv_mflow_pr_relabel(int u) {
    int mh = lv.size()*2;
    for(int v=0; v<lv.size(); v++) {
        if(cfm[u][v] > 0) {
            mh = min(mh, h[v]);
        }
    }
    h[u] = mh+1;
}

void Graph::lv_mflow_r2f(int s, int t) {
    ef = vector<double>(lv.size(), 0); //结点溢出流
    fm = Awfm(lv.size(), ef); //流矩阵
    cfm = fm;  //残存容量
    h=vector<int>(lv.size(), 0); //结点高度
    //Glv nv(lv); //邻接结点链表数组
    auto cmp = [this](int const u, int const v) -> bool { return h[u]<h[v]; };
    using PQ=PQueue<int, decltype(cmp)>;
    vector<PQ> cpqv(lv.size(), PQ(cmp)); //残存邻接节点优先队列列表
    //初始化残存容量矩阵, 节点邻接链表
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            cfm[i][*it] = wcm[i][*it]; 
            if(cfm[i][*it]>0 && i!=s) 
                cpqv[i].push_back(*it);
        }   
    }
    //调整和结点s相关的预流、残存流量、残存邻接节点、超额流量
    for(auto it=lv[s].begin(); it!=lv[s].end(); it++) {
        fm[s][*it] = wcm[s][*it];
        cfm[s][*it] = 0;
        cfm[*it][s] = wcm[s][*it];
        if(cfm[*it][s] > 0)
            cpqv[*it].push_back(s);
        ef[*it] = fm[s][*it];
        ef[s] -=  fm[s][*it];
    }
    h[s] = lv.size();
    lv2mtx();
    vector<int>L; //主循环结点链表
    for(int i=0; i<lv.size(); i++) {
        if(i==s || i==t) continue;
        L.push_back(i); //头部插入结点i
    }
    for(auto lit = L.begin(); lit != L.end(); ) {
        int oh = h[*lit];
        auto it = cpqv[*lit].begin();
        while(ef[*lit] > 0) {
            if(it == cpqv[*lit].end()) {
                cpqv[*lit].make_heap(); 
                break;
            }else if(h[*lit]==h[*it]+1) {
                if(cfm[*it][*lit] == 0) 
                    cpqv[*it].push_back(*lit);    
                lv_mflow_pr_push(*lit, *it); 
                if(cfm[*lit][*it] == 0) {
                    *it = *cpqv[*lit].rbegin();
                    cpqv[*lit].pop_back();
                }
            }else {
                it++;
            }
        }
        while(ef[*lit] > 0) {
            int v = cpqv[*lit].top();
            if(h[*lit]==h[v]+1) {
                if(cfm[v][*lit] == 0)
                    cpqv[v].push_back(*lit);
                lv_mflow_pr_push(*lit, v); 
                if(cfm[*lit][v] == 0) {
                    cpqv[*lit].pop();
                }
            }else {
                h[*lit] = h[v]+1;
            }
        }
        
        if(h[*lit] > oh) {
            int u = *lit;
            *lit = L[0];
            L[0] = u;
            lit = L.begin();
        }else 
           lit++;
    }
    
}
   
void Graph::lv_mflow_ffek(int s, int t) {
    fm=Awfm(lv.size(), vector<double>(lv.size(), 0)); //流矩阵
    cfm = fm;  //残存容量
    Graph gf; //残存网络
    gf.lv.resize(lv.size());
    Glv lvidx(lv.size(), vector<int>(lv.size()));
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin(); it<lv[i].end(); it++) {
            cfm[i][*it] = wcm[i][*it]; //wcm[i][*it] - fm[i][*it]
            if(cfm[i][*it]>0) { 
                //添加残存边
                gf.lv[i].push_back(*it);
                lvidx[i][*it] = gf.lv[i].size()-1;
            } 
            //这里反向边残存容量为0，无需处理
            //cfm[*it][i] = fm[i][*it] => 0
        }
    }
    lv2mtx(); //获取图的邻接矩阵
    gf.lv_bfs(s); //搜索增广路径
    //循环处理增广路径
    while(gf.bdmpre[t] != -1) {
        int u = gf.bdmpre[t];
        double cfp = cfm[u][t];
        int v=u;
        //获取增广路径的残存容量
        while(v != s) {
            u = gf.bdmpre[v];
            cfp = min(cfm[u][v], cfp);
            v = u;
        }
        //增广处理
        v = t;
        while(v != s) {
            //增广fm
            u = gf.bdmpre[v];
            if(mtx[u][v]) { //平行边
                fm[u][v] += cfp;
            }else { //反向边
                fm[v][u] -= cfp;
            }
            //更新cfm和gf的边
            if(cfm[u][v] > cfp) { //保留该残存边
                cfm[u][v] -= cfp; //减少同向边的残存容量
                if(cfm[v][u] == 0) { //新增反向残存边
                    gf.lv[v].push_back(u);
                    lvidx[v][u] = gf.lv[v].size()-1;
                }
                cfm[v][u] += cfp; //增广反向残存边
            } else { //等于cfp，增广后变为0，直接剔除
                gf.lv[u][lvidx[u][v]] = *gf.lv[u].rbegin();
                lvidx[u][*gf.lv[u].rbegin()] = lvidx[u][v];
                gf.lv[u].pop_back();
            }
            v = u;   
        }
        gf.lv_bfs(s);
    }
    
}
   

bool Graph::lv_has_same_branch(int u, int v) {
    while(u != v && bdmpre[u] != -1) {
        u = bdmpre[u];
    }
    return u==v;
}
void Graph::lv_mssp_bfl(int s) {
    lv_msp_init(s);
    for(int i=1; i<lv.size(); i++) { //进行|V|-1轮松弛操作
        for(int u=0; u<lv.size(); u++) {
            for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
                //这里为了加快运行时间而不直接调用松弛操作
                if(mtpwv[u]<MaxWeight) { 
                    double mpw = mtpwv[u]+wcm[u][*it];
                    if(mpw<mtpwv[*it] && !lv_has_same_branch(u, *it)) {
                        mtpwv[*it] = mpw;
                        bdmpre[*it] = u;
                    }

                }
            }
        }
    }
}
Awfm Graph::lv_amsp_johnson(void) {
    //增加一个新节点
    int sdx = lv.size(); //size and index
    lv.push_back(vector<int>(sdx));
    for(int i=0; i<sdx; i++) {
        lv[sdx][i] = i;
    }
    wcm.push_back(vector<double>(sdx, 0));
    Awfm ampwm;
    if(!lv_msp_bf(sdx)) return ampwm;
    vector<double> hv = mtpwv;
    lv.resize(sdx);
    for(int i=0; i<sdx; i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            wcm[i][*it] += hv[i]-hv[*it];
        }
    }
    amspre.resize(0);
    for(int i=0; i<sdx; i++) {
        lv_msp_dijkstra(i);
        ampwm.push_back(mtpwv);
        amspre.push_back(bdmpre);
    }
    for(int i=0; i<sdx; i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            wcm[i][*it] += hv[*it]-hv[i];
        }
        for(int j=0; j<sdx; j++) {
            if(amspre[i][j] != -1)
                ampwm[i][j] += hv[j]-hv[i];
        }
    }
    
    return ampwm;
    
}
Awfm Graph::lv_amsp_fw(void) {
    Awfm m;
    lv_amsp_init(m);
    amspre.resize(lv.size());
    for(int i=0; i<lv.size(); i++) {
        amspre[i].resize(lv.size());
        for(int j=0; j<lv.size(); j++) {
            amspre[i][j] = -1;
        }
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            amspre[i][*it] = i;
        }
        amspre[i][i] = -1;
    }
    for(int k=0; k<lv.size(); k++) {
        for(int i=0; i<lv.size(); i++) {
            for(int j=0; j<lv.size(); j++) {
                if(m[i][k]<MaxWeight && m[k][j]<MaxWeight) {
                    double mspw = m[i][k]+m[k][j];
                    if(mspw < m[i][j]) {
                        m[i][j] = mspw;
                        amspre[i][j] = amspre[k][j];
                    }
                    
                }
            }
        }
    }
    return m;
}
void Graph::lv_amsp_eadd(Awfm &m1, Awfm &m2) {
    for(int i=0; i<lv.size(); i++) {
        for(int j=0; j<lv.size(); j++) {
            m2[i][j] = MaxWeight;
            for(int k=0; k<lv.size(); k++) {
                if(m1[i][k]<MaxWeight && m1[k][j]<MaxWeight) {
                    m2[i][j] = min(m2[i][j], m1[i][k]+m1[k][j]);
                }
            }
        }
    }
}


void Graph::lv_amsp_init(Awfm &m) {
    m.resize(lv.size());
    for(int i=0; i<lv.size(); i++) {
        m[i].resize(lv.size());
        for(int j=0; j<lv.size(); j++) {
            m[i][j] = MaxWeight;
                
        }
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            m[i][*it] = wcm[i][*it];
        }
        //必须在最后，以覆盖可能的自循环节点
        m[i][i] = 0; 
    }
    
}
Awfm Graph::lv_amsp(void) {
    Awfm ma[2];
    lv_amsp_init(ma[0]);
    ma[1].resize(lv.size());
    for(int i=0; i<lv.size(); i++) {
        ma[1][i].resize(lv.size());
    }
    int ec = 1;
    int idx = 0;
    while(ec<lv.size()-1) {
        lv_amsp_eadd(ma[idx], ma[!idx]);
        idx = !idx;
        ec *= 2;
    }
    return ma[idx];
}
    
Glv Graph::lv_mst_kruskal(void) {
    Glv mlv(lv.size());
    if(lv.size()<1) return mlv;
    DisjointSet vsets(lv.size());
    
    vector<GEdge> ev; //使用自定义边
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            if(*it > i) //只取对角线的上半部分(无向图);
                ev.push_back(GEdge{i, *it});
                
        }
    }
    sort(ev.begin(), ev.end(),
        [this](GEdge const &e1, GEdge const &e2) -> bool {
            return wcm[e1[0]][e1[1]] < wcm[e2[0]][e2[1]];
        });
    for(int i=0; i<ev.size(); i++) {
        int vs1 =  vsets.find(ev[i][0]);
        int vs2 =  vsets.find(ev[i][1]);
        if(vs1 == vs2) continue;
        mlv[ev[i][0]].push_back(ev[i][1]);
        mlv[ev[i][1]].push_back(ev[i][0]);
        vsets.djs_union(vs1, vs2);
    }
    return mlv;
}
void Graph::lv_mst_prim(int s) {
    bdmpre.resize(lv.size());
    mtpwv.resize(lv.size());
    //vector<int>vque;
    PQueueWidx vque(CmpFunc{[this](int a, int b)->bool {return mtpwv[a]<mtpwv[b];} });
    //vector<int>vqidx(lv.size());
    vector<bool> vqenv(lv.size(), true);
    for(int i=0; i<lv.size(); i++) {
        bdmpre[i] = -1;
        mtpwv[i] = MaxWeight;
        vque.push_back(i);
    }
    mtpwv[s] = 0;
    //vqueue_up_fix(vque, vqidx, vqidx[s], mtpwv);
    vque.make_heap();
    while(!vque.empty()) {
        //int u = vdequeue(vque, vqidx, mtpwv);
        int u = vque.dequeue();
        //vqidx[u] = -1;
        vqenv[u] = false;
        for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
            //if(vqidx[*it] == -1) continue;
            if(!vqenv[*it]) continue;
            //到前驱可能的最小权重
            double mpw = u<*it ?wcm[u][*it]: wcm[*it][u];
            if(mpw < mtpwv[*it]) {
                mtpwv[*it] = mpw;
                //vqueue_up_fix(vque, vqidx, vqidx[*it], mtpwv);
                vque.up_fix_heap(*it);
                bdmpre[*it] = u;
            }
        }
    }
    
}

void Graph::lv_tarjan_edcc(void) {
    lv_tarjan_bridge();
    vcc.resize(lv.size());
    ccc=0;
    dt = vector<int>(lv.size(), 0);
    time = 0;
    for(int i=0; i<lv.size(); i++) {
        if(!dt[i]) {
            lv_tarjan_edcc_core(i);
            ccc++;
        }
    }
}


void Graph::lv_tarjan_edcc_core(int i) {
    dt[i] =  ++time;
    vcc[i] = ccc;
    for(int j=head[i]; ~j; j=ev[j][1]) {
        if(etv[j]==GETREE) continue; //割边
        if(!dt[ev[j][0]])  {
            lv_tarjan_edcc_core(ev[j][0]);
        }
    }
}

void Graph::lv_tarjan_ddcc(void) {
    dt = vector<int>(lv.size(), 0);
    low.resize(lv.size());
    time = 0;
    bdmpre = vector<int>(lv.size(), -1);
    ddcc.resize(0);
    vs = {};
    for(int i=0; i<lv.size(); i++) {
        if(dt[i] == 0) {
            if(lv[i].size()==0) {
                ddcc.push_back(vector<int>{i});
            }else {
                lv_tarjan_ddcc_core(i);
                vs.pop(); //弹出根结点
            }
        }
    }
}

void Graph::lv_tarjan_ddcc_core(int i) {
    dt[i] = low[i] = ++time;
    vs.push(i);
    for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
        if(dt[*it] == 0) {
            lv_tarjan_ddcc_core(*it);
            low[i] = min(low[i], low[*it]);
            if(low[*it]>=dt[i]) { //i为割点或dfs根
                ddcc.push_back(vector<int>{});
                auto dcit = ddcc.rbegin();
                int u;
                do {
                    u = vs.top(); vs.pop();
                    dcit->push_back(u);
                }while(u!=*it);
                dcit->push_back(i);
            }
        }else if(bdmpre[i] != *it) {
            low[i] = min(low[i], dt[*it]);
        }
    }
    
}

void Graph::lv_tarjan_bridge(void) {
    dt = vector<int>(lv.size(), 0);
    low.resize(lv.size());
    time = 0;
    bdmpre = vector<int>(lv.size(), -1);
    etv = vector<GEType>(lv.size(), GEACCORSS); //GEACCORSS代表非割边，GETREE带表割边
    for(int i=0; i<lv.size(); i++) {
        if(!dt[i]) {
            lv_tarjan_bridge_core(i);
        }
    }
}

void Graph::lv_tarjan_bridge_core(int u) {
    dt[u] = low[u] = ++time;
    for(int j=head[u]; ~j; j=ev[j][1]) {
        int v = ev[j][0];
        if(dt[v]==0) {
            lv_tarjan_bridge_core(v);
            low[u] = min(low[u], low[v]);
            if(dt[u]<low[v]) { //割边
                etv[j] = etv[j^1] = GETREE;
            }
        }else if(bdmpre[u]!=v) {
            low[u] = min(low[u], dt[v]);
        }
    }             
}

void Graph::lv_tarjan_cdot(void) {
    dt = vector<int>(lv.size(), 0);
    low.resize(lv.size());
    vc = vector<GVColor>(lv.size(), GVWHITE); //这里用黑色标记割点
    bdmpre = vector<int>(lv.size(), -1);
    for(int i=0; i<lv.size(); i++) {
        if(dt[i] == 0) {
            lv_tarjan_cdot_core(i);
        }  
    }
}

void Graph::lv_tarjan_cdot_core(int i) {
    dt[i] = low[i] = ++time;
    int childs = 0;
    for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
        if(dt[*it] == 0) {
            bdmpre[*it] = i;
            lv_tarjan_cdot_core(*it);
            low[i] = min(low[i], low[*it]);
            if(dt[i]<=low[i] && (bdmpre[i]!=-1 || ++childs>1)) {
                vc[i] = GVBLACK;
            }
        }else if(bdmpre[i]!=*it) {
            low[i] = min(low[i], dt[*it]);
        }
    }
}



void Graph::lv_tarjan_scc(void) {
    dt = vector<int>(lv.size(), 0);
        //用来记录发现时间, 也用来标记是否已经被发现。
    time = 0;
    ccc = 0;
    vs = {};
    low.resize(lv.size());
    vc = vector<GVColor>(lv.size(), GVWHITE);
        //这里用来标记是否已经入栈, 用于判环
    vcc.resize(lv.size());
    for(int i=0; i<lv.size(); i++) {
        if(dt[i] == 0)
            lv_tarjan_scc_core(i);
    }
}
void Graph::lv_tarjan_scc_core(int i) {
    vc[i] = GVBLACK; 
    dt[i] = low[i] = ++time; 
    vs.push(i);
    for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
        if(vc[*it] == GVBLACK) { //形成了环
            low[i] = min(low[i], dt[*it]);
        }else if(dt[*it] == 0) {
            lv_tarjan_scc_core(*it);
            low[i] = min(low[i], low[*it]);
        }
    }
    if(low[i] == dt[i]) { //环的入点/scc的根
        int u;
        do {
            u = vs.top();
            vs.pop();
            vcc[u] = ccc;
            vc[u] = GVWHITE; //已经不再栈中, 不能再用于判环
        }while(u!=i);
        ccc++;
    }
}
vector<int> Graph::lv_strong_con_compts(void) {
    lv_dfs_nor_noet();
    Graph g;
    g.lv = lv_trans();
    g.lv_dfs_nor_noet_with_order(tporder);
    return g.vcc;
}

Gmtx Graph::mtx_trans(void) {
    Gmtx mtxt(lv.size(), vector<bool>(lv.size()));
    for(int i=0; i<mtx.size(); i++) {
        for(int j=0; j<mtx.size(); j++) {
            mtxt[j][i] = mtx[i][j];
        }
    }
    return mtxt;
}

Gmtx Graph::mtx_square(void) {
    Gmtx mtx2 = mtx;
    for(int i=0; i<mtx.size(); i++) {
        for(int j=0; j<mtx.size(); j++) {
            if(mtx[i][j]) {
                for(int k=0; k<mtx.size(); k++) {
                    if(mtx[j][k])
                        mtx2[i][k] = true;
                }
            }
        }
    }
    return mtx2;
}

bool Graph::mtx_has_usink(void) {
    /**************
    *通用汇点：出度为0，入度为|V|-1
    *当循环结束时有：
    *1、对于任意点ki=0->i-1, 存在x belong2 {0->|V|-1}, 满足g[ki][x] = ture
    *   因此{0..i-1}都不是通用汇点
    *2、如果i<|V|，则j=|V| ==>当j取0到|V|-1任意值kj时, 存在ki属于{0, i}使得
        mtx[ki][kj]=false, 只有这样j才能增大到|V|, 考虑当kj取{i+1->|V|-1}时, 这时
        存在ki of {0, i}满足 ki<kj且mtx[ki][kj] = false, 至少有一个点(非kj)无法到
        达kj, 因此kj(i+1到|V|-1)不是通
        用汇点。
     因此最后只需要判断点i是否为通用汇点即可
    ***************/
    int i=0, j=0;
    while(i<mtx.size() && j<mtx.size()) {
        if(mtx[i][j]) { //排除i(存在出度j)
            i++;
        }else { //如果i!=j则排除j(缺少入度i)
            j++;
        }
    }

    
    if(i==mtx.size()) 
        //0->|V|-1(i-1)都不是
        return false;
        
    /**********
    *0-i-1, i+1->|V|-1都不是
    *判断i是否为汇点
    ***********/
    //1)检查入度=|V|-1
    int k;
    for(k=0; k<mtx.size(); k++) {
        if(k==i) continue;
        if(!mtx[k][i]) return false;
    }
    //2)检查出度=0
    for(k=0; k<mtx.size(); k++) {
        if(mtx[i][k]) return false;
    }

    return true;
}

bool Graph::mtx_has_usink0(void) {
    int i=0, j=0;
    while(i<mtx.size() && j<mtx.size()) {
        if(mtx[i][j]) {
            if(i==j) {
                i++; 
                j++;
            }else {
                i=j;
            }
        }else {
            j++;
        }
    }
    if(i==mtx.size()) 
        return false;
        
    int k;
    for(k=0; k<mtx.size(); k++) {
        if(k==i) continue;
        if(!mtx[k][i]) return false;
    }
    
    for(k=0; k<i; k++) {
        if(mtx[i][k]) return false;
    }

    return true;
}

Glv Graph::lv_square(void) {
    lv2mtx();
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            for(auto jt = lv[*it].begin(); jt!=lv[*it].end(); jt++) {
                mtx[i][*jt] = true;
            }
        }
    }
    Graph g; g.mtx = mtx;
    g.mtx2lv();
    return g.lv;
}


Glv Graph::lv_trans(void) {
    Glv lvt(lv.size());
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            lvt[*it].push_back(i);
        }
    }
    return lvt;
}


void Graph::lv_trim(void) {
    vector<int> visitor(lv.size(), -1);
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); ) {
            if(visitor[*it]<i && i!=*it) {
                visitor[*it] = i;
                it++;
            }else {
                *it = *lv[i].rbegin();
                lv[i].pop_back();
            }
        }
    }
}

void Graph::lv_bfs(int s) {
    bdmpre = vector<int>(lv.size(), -1);
    bd.resize(lv.size());
    vc = vector<GVColor>(lv.size(), GVWHITE); //用于标记是否已经访问过
    bd[s] = 0;
    queue<int> bq;
    bq.push(s);
    vc[s] = GVBLACK;
    while(!bq.empty()) {
        int u = bq.front();
        bq.pop();
        for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
            if(vc[*it] == GVBLACK) continue;
            bd[*it] = bd[u]+1;
            bdmpre[*it] = u;
            bq.push(*it);
            vc[*it] = GVBLACK;
        }
    }
}
    
void Graph::lv2mtx(void) {
    mtx.resize(lv.size());
    for(int i=0; i<lv.size(); i++) {
        mtx[i] = vector<bool>(lv.size(), false);
    }
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin();  it!=lv[i].end(); it++) {
            mtx[i][*it] = true;
        }
    }
}
    
void Graph::mtx2lv(void) {
    lv.resize(mtx.size());
    for(int i=0; i<mtx.size(); i++) {
        lv[i].resize(0);
        for(int j=0; j<mtx.size(); j++) {
            if(mtx[i][j])
                lv[i].push_back(j);
        }
    }
}


void Graph::lv_msp_dijkstra(int s) {
    lv_msp_init(s);
    PQueueWidx vque(CmpFunc{[this](int a, int b)->bool {return mtpwv[a]<mtpwv[b];}});
    vector<bool> vqenv(lv.size(), true);
    for(int i=0; i< lv.size(); i++) {
        vque.push_back(i);
    }
    vque.make_heap();
    while(!vque.empty()) {
        int u = vque.dequeue();
        for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
            if(vqenv[*it] && mtpwv[u]+wcm[u][*it]<mtpwv[*it]) {
                mtpwv[*it] = mtpwv[u]+wcm[u][*it];
                bdmpre[*it] = u;
                vque.up_fix_heap(*it);
            }
        }
    }
}
void Graph::lv_tp_order(void) {
    int tpc = 0; //拓补排序计数
    tporder.resize(lv.size());
    vector<int> vinc(lv.size(), 0); //记录点的入度
    for(int i=0; i<lv.size(); i++) {
        for(auto it=lv[i].begin(); it!=lv[i].end(); it++) {
            vinc[*it]++;
        }
    }
    queue<int> vque; //入度为0的结点的队列
    for(int i=0; i<lv.size(); i++) {
        if(vinc[i] == 0) {
            vque.push(i);
        }
    }
    while(!vque.empty()) {
        int u = vque.front();
        tporder[tpc++] = u;
        vque.pop();
        for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
            vinc[*it]--;
            if(vinc[*it]==0) {
                vque.push(*it);
            }
        }
    }
    
}
void Graph::lv_dag_msp(int s) {
    lv_tp_order();
    lv_msp_init(s);
    for(auto vit=tporder.begin(); vit!=tporder.end(); vit++) {
        for(auto it=lv[*vit].begin(); it!=lv[*vit].end(); it++) {
            lv_msp_relax(*vit, *it);
        }
    }
    
}

void Graph::lv_dfs_visit(int u) {
    dt[u] = time++;
    vc[u] = GVGREY;
    for(int j=head[u]; ~j; j=ev[j][1]) {
        int v = ev[j][0];
        if(vc[v]==GVWHITE) {
            bdmpre[v] = u;
            etv[j] = GETREE;
            vcc[v] = vcc[u];
            lv_dfs_visit(v);
        }else {
            lv_dfs_deal_vgb(u, j);
        }
    }
    ft[u] = time++;
    tporder[--tpc] = u;
    vc[u] = GVBLACK;
}


void Graph::lv_dfs_noet_visit(int u) {
    dt[u] = time++;
    vc[u] = GVGREY;
    for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
        if(vc[*it] == GVWHITE) {
            bdmpre[*it] = u;
            vcc[*it] = vcc[u];
            lv_dfs_noet_visit(*it);
        }
    }
    ft[u] = time++;
    tporder[--tpc] = u;
    vc[u] = GVBLACK;
}

void Graph::lv_dfs_deal_vgb(int u, int j) {
        int v = ev[j][0];
        if(vc[v] == GVGREY) {
            /***************************
            if(is_dird) {
                et[u][v] = GEBACK; 
            }else {
                if(et[v][u] = GETREE) {
                    et[u][v] = GETREE;
                }else {
                    et[u][v] = GEBACK;
                    //et[v][u] = GEBACK;
                }     
            }   
            *********************************/
            if(!is_dird && etv[j^1] == GETREE)
                etv[j] = GETREE;
            else
                etv[j] = GEBACK;
        }else { //v为黑色
            if(!is_dird) {  //无向图(两点互通，不可能异分支)
                //v为u的间接(树中间接)后代，在处理v时有et[v][u] = GEBACK
                //u->v为同一条边也应被标记为后向边
                etv[j] = GEBACK;
                
            }else if(dt[u]<dt[v]) {//有向图且共分支 
                    etv[j] = GEFRONT;
                
            } //else 默认就是GEACCORSS
                //etv[j] = GEACCORSS;    
    
        }

}


void Graph::lv_dfs_noet_init(void) {
    bdmpre.resize(lv.size()); //记录dfs过程中结点的前驱
    dt.resize(lv.size()); //dfs discover time
    ft.resize(lv.size()); //dfs finish time
    vc = vector<GVColor>(lv.size(), GVWHITE); //dfs vertex color
    vcc.resize(lv.size()); //dfs vertex connected componet id

    tpc = lv.size(); //拓补排序计数
    ccc = 0; //dfs connected componet id
    time = 0; //dfs 时间计数
    tporder.resize(lv.size());

}
void Graph::lv_dfs_init(void) {
    lv_dfs_noet_init();
    lv2lfs();
    etv = vector<GEType>(ev.size(), GEACCORSS); //dfs egde type
}

void Graph::lv_dfs(void) {
    lv_dfs_init();
    for(int i=0; i<lv.size(); i++) {
        if(vc[i] == GVWHITE) {
            vcc[i] = ccc++;
            bdmpre[i] = -1;
            lv_dfs_visit(i);
        }
    }
}


void Graph::lv_dfs_noet(void) {
    lv_dfs_noet_init();
    for(int i=0; i<lv.size(); i++) {
        if(vc[i] == GVWHITE) {
            vcc[i] = ccc++;
            bdmpre[i] = -1;
            lv_dfs_noet_visit(i);
        }
    }
}

void Graph::lv_dfs_nor_with_order(vector<int> &ord) {
    lv_dfs_init();
    vs = {}; //点栈用于模拟递归
    stack<int> es; //待处理邻接边栈，用于模拟递归
    for(auto uit=ord.begin(); uit!=ord.end(); uit++) {
        //黑色已处理直接跳过
        if(vc[*uit] == GVBLACK) continue;
        vc[*uit] = GVGREY;
        dt[*uit] = time++;
        vcc[*uit] = ccc++;
        vs.push(*uit);
        es.push(head[*uit]);
        bdmpre[*uit] = -1;
        lv_dfs_nor_lpcore(es);
    }
}


void Graph::lv_dfs_nor_noet_with_order(vector<int> &ord) {
    lv_dfs_noet_init();
    vs = {};
    stack<GVit> its;
    for(auto uit=ord.begin(); uit!=ord.end(); uit++) {
        //黑色已处理直接跳过
        if(vc[*uit] == GVBLACK) continue;
        vc[*uit] = GVGREY;
        dt[*uit] = time++;
        vcc[*uit] = ccc++;
        vs.push(*uit);
        its.push(lv[*uit].begin());
        bdmpre[*uit] = -1;
        lv_dfs_nor_noet_lpcore(its);
    }
}

void Graph::lv_dfs_nor(void) {
    lv_dfs_init();
    vs = {};
    stack<int> es;
    for(int i=0; i<lv.size(); i++) {
        //黑色已处理直接跳过
        if(vc[i] == GVBLACK) continue;
        vc[i] = GVGREY;
        dt[i] = time++;
        vcc[i] = ccc++;
        vs.push(i);
        es.push(head[i]);
        bdmpre[i] = -1;
        lv_dfs_nor_lpcore(es);
    }
}


void Graph::lv_dfs_nor_noet(void) {
    lv_dfs_noet_init();
    stack<int> vs;
    stack<GVit> its;
    for(int i=0; i<lv.size(); i++) {
        //黑色已处理直接跳过
        if(vc[i] == GVBLACK) continue;
        vc[i] = GVGREY;
        dt[i] = time++;
        vcc[i] = ccc++;
        vs.push(i);
        its.push(lv[i].begin());
        bdmpre[i] = -1;
        lv_dfs_nor_noet_lpcore(its);
    }
}

void Graph::lv_dfs_nor_lpcore(stack<int> &es) {
    while(!vs.empty()) {
        NEWV:
        int u = vs.top();
        int &eid = es.top();
        while(~eid) {
            int v = ev[eid][0];
            if(vc[v] == GVWHITE) {
                vc[v] = GVGREY;
                dt[v] = time++;
                vcc[v] = vcc[u];
                bdmpre[v] = u;
                etv[eid] = GETREE;
                vs.push(v);
                eid = ev[eid][1]; //注意这里的eid为引用，更新为u的下一个待处理邻节边
                es.push(head[v]);
                goto NEWV;
            }else {
                lv_dfs_deal_vgb(u, eid);
            }
            eid = ev[eid][1];
        }
        vs.pop();
        es.pop();
        vc[u] = GVBLACK;
        ft[u] = time++;
        tporder[--tpc] = u;
    
    }  
}


void Graph::lv_dfs_nor_noet_lpcore(stack<GVit> &its) {
    while(!vs.empty()) {
        NEWV:
        int u = vs.top();
        GVit &it = its.top();
        while(it != lv[u].end()) {
            int v = *it;
            if(vc[v] == GVWHITE) {
                vc[v] = GVGREY;
                dt[v] = time++;
                vcc[v] = vcc[u];
                bdmpre[v] = u;
                vs.push(v);
                it++; //注意这里it为前its栈顶的引用(更新为u的下一个待处理邻节点)
                its.push(lv[v].begin());
                goto NEWV;
            }
            it++;
        }
        vs.pop();
        its.pop();
        vc[u] = GVBLACK;
        ft[u] = time++;
        tporder[--tpc] = u;
    
    }  
}

bool Graph::lv_spath_print(int s, int d) {
    if(d==s) printf("%d", s);
    else if(bdmpre[d] == -1) {
        printf("No search-path from %d to %d", s, d);
        return false;
    }else { 
        lv_spath_print(s, bdmpre[d]);
        printf("->%d", d);
    }
    return true;
}
bool Graph::lv_spath_printc(int s, int d) {
    if(d==s) printf("%c", s+fvc);
    else if(bdmpre[d] == -1) {
        printf("No search-path from %c to %c", s+fvc, d+fvc);
        return false;
    }else {
        lv_spath_printc(s, bdmpre[d]);
        printf("->%c", d+fvc);
    }
    return true;
}

void Graph::lv_msp_init(int s) {
    bdmpre.resize(lv.size());
    mtpwv.resize(lv.size());
    for(int i=0; i<lv.size(); i++) {
        bdmpre[i] = -1;
        mtpwv[i] = MaxWeight;
    }
    mtpwv[s] = 0;

}
void Graph::lv_msp_relax(int u, int v) {
    if(mtpwv[u] != MaxWeight && mtpwv[v]>mtpwv[u]+wcm[u][v]) {
        mtpwv[v] = mtpwv[u]+wcm[u][v];
        bdmpre[v] = u;
    }
}

bool Graph::lv_msp_bf(int s) {
    lv_msp_init(s);
    for(int i=1; i<lv.size(); i++) {
        for(int u=0; u<lv.size(); u++) {
            for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
                lv_msp_relax(u, *it);
            }
        }
    }
    for(int u=0; u<lv.size(); u++) {
        for(auto it=lv[u].begin(); it!=lv[u].end(); it++) {
            if(mtpwv[u]!=MaxWeight && mtpwv[*it]>mtpwv[u]+wcm[u][*it])
                return false;
        }
    }
    return true;
}


